Restoring three dimensional (3-D) information from a stereo image is an important task in 3-D image processing. The basis for stereo image is the fact that a real-world point projects to a unique pair of corresponding pixels in stereo images. As a result, it may be possible to restore 3-D information if the pixels in a left and right image corresponding to the same real-world point are determined. Determining the location of pixels in each camera image that are projection of a same real-world point is, generally, referred to as a correspondence problem. Solving a correspondence problem includes estimation of a disparity map.
The difference in the position of the two corresponding points of the same real-world image in the left and right view images is, generally, referred to as disparity or parallax. A map of disparity in the projection of several real-world points in the left and right image may be referred to as a disparity map. Some techniques to generate disparity map include local, global, and iterative approaches. In a local approach, the estimation of the disparity map depends on the intensity values within a finite window and the computational cost is thus low. On the other hand, the global approaches use non-local constraints to reduce sensitivity to local regions such as occluded and textureless regions and the computational cost of the global approach is thus high compared to the local approach. In between the local and global approaches is the iterative approach. The iterative approaches such as coarse-to-fine techniques, typically, operate on an image pyramid in which the results from the coarser levels are used to define more local search at finer levels. Improving the efficiency of such iterative approaches is therefore important.